package com.cheng.dataStructure.linkedlist;

/**
 * @User Administrator
 * @Classname SingleLinkedListDemo01
 * @Project Data-structure-and-algorithm
 * @Description 添加v1.0：用单链表实现水浒英雄的无序插入，即插入顺序和英雄排名无关,每次添加到添加到链表最后
 *              添加v2.0：添加的顺序由英雄的排名决定，如果插入前已经存在则报错
 * @Author wpcheng
 * @Create 2021-06-23-9:39
 * @Version 1.0
 */

/*
* 单链表的概念：
* 1.链表是以节点的方式来储存，是链式存储
* 2.每个节点包含data域，next域：指向下一个节点
* 3.链表的各个节点在内存中并不一定是连续存储的
* 4.链表分为带头节点的链表和没有头结点的链表
* */

public class SingleLinkedListDemo01 {
    public static void main(String[] args) {
        //创建节点测试
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");

        //创建一个链表
        SingleLinkedList list = new SingleLinkedList();
//        添加英雄节点 添加v1.0
//        list.add(heroNode1);
//        list.add(heroNode2);
//        list.add(heroNode4);
//        list.add(heroNode3);

        /*链表添加显示结果：无序
         * HeroNode{id=1, name='宋江', nickname='及时雨'}
         * HeroNode{id=2, name='卢俊义', nickname='玉麒麟'}
         * HeroNode{id=4, name='林冲', nickname='豹子头'}
         * HeroNode{id=3, name='吴用', nickname='智多星'}
         * */


        //添加英雄节点 添加v2.0,升级版
        list.addById(heroNode1);
        list.addById(heroNode2);
        list.addById(heroNode4);
        list.addById(heroNode3);

        /*链表添加显示结果：有序
         * HeroNode{id=1, name='宋江', nickname='及时雨'}
         * HeroNode{id=2, name='卢俊义', nickname='玉麒麟'}
         * HeroNode{id=3, name='吴用', nickname='智多星'}
         * HeroNode{id=4, name='林冲', nickname='豹子头'}
         * */

        //输出链表
        list.list();

        //修改英雄节点信息
        HeroNode heroNode = new HeroNode(1, "宋水", "玉麒麟");
        list.update(heroNode);

        System.out.println("===========修改后的链表为===========");
        //输出链表
        list.list();

        //查找id为1的节点
        list.find(1);

        list.del(1);
        list.del(4);
        list.del(2);
        list.del(3);

        System.out.println("===========删除后的链表为===========");
        list.list();

    }
}
//创建单链表SingleLinkedList，来对英雄进行操作
class SingleLinkedList{
    //初始化一个头结点，头结点不要移动(否则找不到整条链表的位置)，也不存放数据
    private HeroNode head = new HeroNode(0,"","");

    //返回头结点
    public HeroNode getHead(){
        return head;
    }


    /** 添加v1.0：用单链表实现水浒英雄的无序插入，即插入顺序和英雄排名无关,每次添加到添加到链表最后
     * @param heroNode
     * 添加节点思路：
     * 1.找到链表的最后一个节点
     * 2.将最后一个节点的next域指向要添加的节点
     */
    public void add(HeroNode heroNode){
        //定义一个辅助变量temp，并指向头结点head
        HeroNode temp = head;
        //循环查找链表最后一个节点
        while (true){
            //如果找到链表最后一个节点，就退出循环
            if (temp.next == null ){
                break;
            }
            //如果没有找到就往后移，并继续循环查找
            temp = temp.next;
        }
        //让最后一个节点的next域指向要添加的节点
        temp.next = heroNode;

    }

    /**添加v2.0：添加的顺序由英雄的排名决定，如果存在则报错
     * @param heroNode
     * 添加思路：
     * 1.确定新节点添加的位置，通过辅助变量temp遍历来确定，temp位于添加位置的前面
     * 2.新节点.next = temp.next，先让新节点的next指向temp的下一个节点
     * 3.temp.next = 新节点，再把新节点插入到temp后面
     */
    public void addById(HeroNode heroNode){
        //定义辅助变量
        HeroNode temp = head;
        //定义标志位，如果为false，说明新节点的编号在链表中不存在，为true说明在链表中已经存在
        Boolean flag = false;
        while(true){
            //temp是链表的最后一个节点
            if (temp.next == null){
                break;
            }
            //插入位置确定
            if (temp.next.id > heroNode.id){
                break;
            }
            //新节点的编号在链表中已经存在
            if(temp.next.id == heroNode.id){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("新节点的编号"+heroNode.id+"在链表中已经存在，插入失败");
        }else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    /**
     * 根据英雄节点的ID删除节点
     * 思路分析：
     * 1.确定要删除节点的前一个节点，通过定义辅助变量temp遍历来确定
     * 2.temp.next = temp.next.next 将temp指向被删除节点的next域指向删除节点的后一个节点的next域
     * 3.被删除的节点，因为没有其他引用指向，将会被垃圾回收机制处理
     * @param id
     */
    public void del(int id){
        HeroNode temp = head;
        //标志位，标识是否找到删除节点的前一个节点
        boolean flag = false;
        while(true){
            //temp已经指向了链表的最后
            if (temp.next == null){
                break;
            }
            if(temp.next.id == id){
                //找到temp，标志位改为true
                flag = true;
                break;
            }
            //temp后移
            temp = temp.next;
        }
        if(flag){
            temp.next = temp.next.next;
        }else {
            System.out.println("要删除的节点"+id+"不存在，删除失败");
        }
    }

    /**
     * 修改英雄节点信息：根据id修改
     * @param newHeroNode
     */
    public void update(HeroNode newHeroNode){
        //判断是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //根据新节点id找到链表中对应要修改的节点
        HeroNode temp = head.next;
        Boolean flag = false;//是否找到该节点
        while (true){
            if (temp == null){
                break;//遍历完成
            }
            //找到要修改的节点
            if (temp.id == newHeroNode.id){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else {
            System.out.println("没有找到编号为"+newHeroNode.id+"的节点，修改失败");
        }
    }

    /**
     * 根据id查找节点
     * @param id
     */
    public HeroNode find(int id){
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            if (temp.next == null){
                break;
            }
            if (temp.id == id){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println(temp);
        }else {
            System.out.println("没找到id为"+id+"的节点");
        }
        return temp;
    }


    //显示链表
    public void list(){
        //如果链表为空
        if (head.next==null){
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                return;
            }
            System.out.println(temp);
            //每输出一个节点，就将temp后移一下，不然会陷入死循环，导致不能输出
            temp = temp.next;
        }
    }
}

//创建英雄节点，每个HeroNode对象都是一个英雄
class HeroNode{
    public int id;//英雄排名
    public String name;//英雄姓名
    public String nickname;//英雄昵称
    public HeroNode next;//指向下一个节点

    public HeroNode(int id, String name, String nickname) {
        this.id = id;
        this.name = name;
        this.nickname = nickname;

    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}